//
// Created by TNJ on 2021/6/27.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//插入排序
void insert_sort(int *arr, int length, int start, int gap){
    if(arr == NULL || length <= 0 || start < 0 || gap <= 0){
        return;
    }
    int i = 0, j = 0;
    int value = 0;

    for(i = start; i < length - gap; i += gap){
        value = arr[i + gap];
        for(j = i; j >= start; j -= gap){
            if(value < arr[j]){
                arr[j + gap] = arr[j];
            }else{
                break;
            }
        }
        arr[j + gap] = value;
    }
}

//希尔排序
void shell_sort(int *arr, int length){
    if(arr == NULL || length <= 0){
        return;
    }
    int gap = 0, start = 0;
    int count = 0;
    for(gap = length / 2; gap > 0; gap /= 2){
        start = 0;
        for(count = 0; count < gap; count++){
            insert_sort(arr, length, start, gap);
            start++;
        }
    }
}